package lanQiaoBei.violent_recursion;

import java.util.ArrayList;
import java.util.List;

/*
* 利用暴力递归(尝试)找出一个字符串的所有排列组合(不考虑顺序)
* abcde
* */
public class StrPermutation {
    public static void main(String[] args) {
           realize("abccc");
    }
    public static void realize(String str){
        char[] chars = str.toCharArray();
        List<String>res=new ArrayList<>();
        fun(chars,0,res);
        System.out.println(res);
    }

    private static void fun(char[] chars, int i, List<String> res) {
            if(i==chars.length){
                res.add(String.valueOf(chars));
            }
        boolean[]isVisited=new boolean[26];
        for (int j = i; j <chars.length; j++) {
            if(!isVisited[chars[j]-'a']){//剪枝
                swap(i,j,chars);
                fun(chars,i+1,res);
                swap(i,j,chars);
            }
            isVisited[chars[j]-'a']=true;
        }
    }

    private static void swap(int i, int j, char[] chars) {
           char temp=chars[i];
           chars[i]=chars[j];
           chars[j]=temp;
    }
}

